Search results for "Rural Postman"
showing 10 items of 17 documents
Drone arc routing problems
2018
[EN] In this article, we present some drone arc routing problems (Drone ARPs) and study their relation with well-known postman ARPs. Applications for Drone ARPs include traffic monitoring by flying over roadways, infrastructure inspection such as by flying along power transmission lines, pipelines or fences, and surveillance along linear features such as coastlines or territorial borders. Unlike the postmen in traditional ARPs, drones can travel directly between any two points in the plane without following the edges of the network. As a consequence, a drone route may service only part of an edge, with multiple routes being used to cover the entire edge. Thus the Drone ARPs are continuous o…
A New Branch-and-Cut Algorithm for the Generalized Directed Rural Postman Problem
2016
The generalized directed rural postman problem, also known as the close-enough arc routing problem, is an arc routing problem with some interesting real-life applications, such as routing for meter reading. In this article we introduce two new formulations for this problem as well as various families of new valid inequalities that are used to design and implement a branch-and-cut algorithm. The computational results obtained on test bed instances from the literature show that this algorithm outperforms the existing exact methods
The directed profitable rural postman problem with incompatibility constraints
2017
[EN] In this paper, we study a variant of the directed rural postman problem (RPP) where profits are asso- ciated with arcs to be served, and incompatibility constraints may exist between nodes and profitable arcs leaving them. If convenient, some of the incompatibilities can be removed provided that penalties are paid. The problem looks for a tour starting and ending at the depot that maximizes the difference between collected profits and total cost as sum of traveling costs and paid penalties, while satisfying remaining incompatibilities. The problem finds application in the domain of road transportation service, and in particular in the context of horizontal collaboration among carriers …
Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem
2017
[EN] The generalized directed rural postman problem is an arc routing problem with many interesting real-life applications, such as routing for meter reading. In this application, a vehicle with a receiver travels through a series of neighborhoods. If the vehicle gets closer than a certain distance to a meter, the receiver is able to record the gas, water, or electricity consumption. Therefore, the vehicle does not need to traverse every street, but only a few, to get close enough to each meter. We study an extension of this problem in which a fleet of vehicles is available. Given the characteristics of the mentioned application, the vehicles have no capacities but there is a maximum distan…
A comparison of two different formulations for Arc Routing Problems on Mixed graphs
2006
[EN] Arc routing problems on mixed graphs have been modelled in the literature either using just one variable per edge or associating to each edge two variables, each one representing its traversal in the corresponding direction. In this paper, and using the mixed general routing problem as an example, we compare theoretical and computationally both formulations as well as the lower bounds obtained from them using Linear Programming based methods. Extensive computational experiments, including some big and newly generated random instances, are presented.
New Heuristic Algorithms for the Windy Rural Postman Problem
2005
[EN] In this paper we deal with the windy rural postman problem. This problem generalizes several important arc routing problems and has interesting real-life applications. Here, we present several heuristics whose study has lead to the design of a scatter search algorithm for the windy rural postman problem. Extensive computational experiments over different sets of instances, with sizes up to 988 nodes and 3952 edges, are also presented. (c) 2004 Elsevier Ltd. All rights reserved.
A branch-and-cut algorithm for the Profitable Windy Rural Postman Problem
2016
[EN] In this paper we study the profitable windy rural postman problem. This is an arc routing problem with profits defined on a windy graph in which there is a profit associated with some of the edges of the graph, consisting of finding a route maximizing the difference between the total profit collected and the total cost. This problem generalizes the rural postman problem and other well-known arc routing problems and has real-life applications, mainly in snow removal operations. We propose here a formulation for the problem and study its associated polyhedron. Several families of facet-inducing inequalities are described and used in the design of a branch-and-cut procedure. The algorithm…
A Branch-Price-and-Cut Algorithm for the Min-Max k -Vehicle Windy Rural Postman Problem
2013
[EN] The min-max k -vehicles windy rural postman problem consists of minimizing the maximal distance traveled by a vehicle to find a set of balanced routes that jointly service all the required edges in a windy graph. This is a very difficult problem, for which a branch-and-cut algorithm has already been proposed, providing good results when the number of vehicles is small. In this article, we present a branch-price-and-cut method capable of obtaining optimal solutions for this problem when the number of vehicles is larger for the same set of required edges. Extensive computational results on instances from the literature are presented.
The mixed general routing polyhedron
2003
[EN] In Arc Routing Problems, ARPs, the aim is to find on a graph a minimum cost traversal satisfying some conditions related to the links of the graph. Due to restrictions to traverse some streets in a specified way, most applications of ARPs must be modeled with a mixed graph. Although several exact algorithms have been proposed, no polyhedral investigations have been done for ARPs on a mixed graph. In this paper we deal with the Mixed General Routing Problem which consists of finding a minimum cost traversal of a given link subset and a given vertex subset of a mixed graph. A formulation is given that uses only one variable for each link (edge or arc) of the graph. Some properties of the…
The General Routing Problem polyhedron: Facets from the RPP and GTSP polyhedra
1998
[EN] In this paper we study the polyhedron associated with the General Routing Problem (GRP). This problem, first introduced by Orloff in 1974, is a generalization of both the Rural Postman Problem (RPP) and the Graphical Traveling Salesman Problem (GTSP) and, thus, is NP -hard. We describe a formulation of the problem such that from every non-trivial facet-inducing inequality for the RPP and GTSP polyhedra, we obtain facet-inducing inequalities for the GRP polyhedron, We describe a new family of facet-inducing inequalities for the GRP, the honeycomb constraints, which seem to be very useful for solving GRP and RPP instances. Finally, new classes of facets obtained by composition of facet-i…